【编译原理】

目录

一、文法的化简与改造

1、文法的实用限制

（1）不含无用产生式

（2）不含有害规则

（3）无用符号和无用产生式的消除

 2、产生式的消除

算法3：     

算法4：ε不属于L(G)

算法5：ε属于L(G)

3、单产生式的消除

算法6：

 4、文法的其他表示方法

（1）{ }

 （2）[ ]

 （3）（ ）

 5、文法和语言的Chomsky分类

（1）0型文法

（2）1型文法

（3）2型文法

（4）3型文法

二、例题

1、G[Z]:Z→(+|-)AB

             A→0|1|2|......|9|AA             B→2|4|6|8         描述的语言特征

2、消除文法的ε产生式，G[S]：S→aBS|b B→cS|ε

3、将文法G[S]改写为等价的正则文法G[S]：S→dABA→aA|aB→Bb| ε

不含无用产生式、不含有害规则。

无用产生式:产生式的左部或右部含有无用符号。

设G=（Vn，Vt，P，S）是一文法，G中的符号x∈Vn∪Vt是有用的，则x 必满足①存在α、β∈V*，有S=*>αxβ ②存在ω∈Vt* 使αxβ=*> ω 称符号x是有用的，否则x是无用的。

形如 U→ U 的规则 (原因①不必要②引起二义性)

算法1：         满足②存在ω∈Vt* 使αxβ=*> ω

文法G=(Vn,Vt,P,S)(假定L(G)≠Φ),得到等价 文 法 G1=(Vn①,Vt,P①,S), 对 于 每 个 X∈Vn① , 都 有w1∈Vt*,满足X=*>w1。

算法2：         满足①存在α、β∈V*，有S=*> αxβ

文法G=(Vn,Vt,P,S)(假定L(G)≠Φ),得到等价文法G′=(Vn′,Vt′,P′,S),对于任一x∈V′,都存在α、β∈V′* ,有S=*> αxβ。

消除步骤：

1、对文法G,执行算法1得到文法G1；

2、对文法G1,执行算法2得到文法G′,为所求。

例：

G[S]: Vn={S,W,U,V} Vt={a,b,c } P={

S→aS︱W︱U, U→a,

V→bV︱ac, W→aW

}

消除无用产生式：

G[S]: Vn={S,U} Vt={a} P={S→aS︱U,U→a}

对G[S]执行算法2.1得到G1[S]: Vn①={U,V,S} Vt={a,b,c } P①={S→aS︱U, U→a, V→bV︱ac }

G1[S]执行算法2.2得到G2[S] Vn′={S,U} Vt′={a} P′={S→aS︱U,U→a}

找出G中满足A=＊>ε的所有A,构成集合W，设G=(Vn,Vt ,P, S) ①作集合W1={A︱A→ε∈P} ②作集合序列Wk+1= Wk∪{B︱B→β∈P且β∈ Wk＋｝ 显然Wk≦ Wk+1（K>=1), 由于Vn有限， 故必存在某i,使得Wi=Wi+1=...., 令W=Wi,对每个A∈W, A=＊>ε 特别：当S∈W,则ε∈L(G); 否则，ε不属于L(G).

设G=(Vn,Vt, P, S), 且ε不属于L(G)，则按下述算法构造G′=(Vn,Vt,P′,S), 使L(G′)=L(G), 且不含ε产生式。

①按算法2.3将Vn分为两个不相交的子集，W及Vn－W ②设X →X1X2...Xm是P中的任一产生式，按下述规则将所有形如 X→Y1Y2...Ym的产生式放入P′中，对于一切1B,B∈Vn}

(2)构造产生式集合 P′=∪{ Ai →α︱ B →α∈P,B∈W(i), α不属于Vn} 此时, P′中已不含任何单产生式.

例：

G[S]: Vn={S,A,B} Vt={a,b} P={

S→AB︱A︱B, A→ab︱aAb B→Bb︱b

}

对G[S]执行算法6得到G1[S]: W(S)={S,A,B} W(A)={A} W(B)={B}

P′={S→AB︱aAb︱ab︱Bb︱b} ∪{A→aAb︱ab} ∪{B→Bb︱b} 为所求, G1[S]与G[S]等价.

规则中提取公因子

文法是一个四元组G=（Vn，Vt，P，Z），乔姆斯基根据文法中P的不同，将文法分为四类,每一种文法对应一种语言。

文法G中规则呈α→β α∈V+，β∈V*，也称短语结构文法（PSG）,对应图灵机确定的语言为0型语言L0

文法G中规则呈α1Aα2→α1βα2 α1，α2∈V*，A∈Vn，β∈V+，也称上下文有关文法(CSG).对应线性界限自动机确定的语言为1型语言L1,也称上下文有关语言。

文法G中规则呈A→β A∈Vn，β∈V+ (或V*)，也称上下文无关文法(CFG).对应下推自动机识别,确定的语言为2型语言L2或上下文无关语言，2型文法在语法分析中用于描述语法类。

文法G中规则呈：

确定的语言为3型语言L3或正则语言，有限自动机识别，3型文法在词法分析中用于描述单词符号。

句子是不能被5整除的偶整数（不以0结尾可以0开头）

解：G[S]: S→aBS|aS|b B→cS

解：设S′→AB 则 S→dS′

A带入S ′ 则 S′→aAB|aB S′→aS′|aB

G[S]: S→dS′ S′→aS′|aB A→aA|a B→bB| ε

消去无用产生式和ε产生式：

G[S]: S→dS′ S′→aS′|aB|a B→bB| b